package math;

/*
 * POJ2055
 */
/**
 * O(n*m^2)
 * 
 * @author yinzichen
 * 
 */

public class GaussModular {

	/**
	 * @param a
	 *            a[n][m+1]
	 * @param n
	 *            number of equations
	 * @param m
	 *            number of variables
	 * @param mod
	 *            number to mod
	 * @return whether has solution
	 */
	boolean gauss(int a[][], int n, int m, int mod) {
		int p = -1, q = 0, i, j;
		int pi[] = new int[m];
		for (i = 0; i < m; i++)
			pi[i] = -1;
		while (++p < m) {
			for (i = q; i < n; i++)
				if (a[i][p] != 0)
					break;
			if (i >= n)
				continue;
			swap(i, q, a);
			for (i = q + 1; i < n; i++) {
				while (a[i][p] != 0) {
					if (a[q][p] > a[i][p])
						for (j = 0; j <= m; j++)
							a[q][j] = (a[q][j] - a[i][j] + mod) % mod;
					else
						for (j = 0; j <= m; j++)
							a[i][j] = (a[i][j] - a[q][j] + mod) % mod;
				}
			}
			pi[p] = q++;
		}
		while (q < n)
			if (a[q++][m] != 0) {
				return false;
			}
		return true;
	}

	void swap(int i, int j, int[][] a) {
		int[] temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}
